class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        memo = dict()

        def bt(nums, i, remain):
            if i == len(nums):
                if remain == 0:
                    return 1
                return 0

            key = f"{i}-{remain}"
            if i in memo:
                return memo[i]
            
            res = bt(nums, i+1, remain-nums[i]) + bt(nums, i+1, remain+nums[i])
            memo[key] = res
            return res
       
        return bt(nums, 0 , target)

if __name__ == '__main__':
    s = Solution()
    nums = [47,30,12,40,10,31,5,12,14,25,45,34,34,31,20,1,33,28,30,30]
    target = 34
    c = s.findTargetSumWays(nums, target)
    print(c)


